package leetcode;

public class LC53 {
    public static void main(String[] args) {
        LC53 lc53 = new LC53();
        System.out.println(lc53.findMin(new int[]{5,4}));
        System.out.println(lc53.findMin(new int[]{4,5,6,7}));
        System.out.println(lc53.findMin(new int[]{4,5,6,7,1,2,3}));
        System.out.println(lc53.search(new int[]{4,5,6,7,0,1,2},0));
        System.out.println(lc53.search(new int[]{4,5,6,7,0,1,2},1));
        System.out.println(lc53.search(new int[]{4,5,6,7,0,1,2},5));
        System.out.println(lc53.search(new int[]{4,5,6,7,0,1,2},4));
        System.out.println(lc53.search(new int[]{4,5,6,7,0,1,2},3));
    }
    /**     LeetCode  33题
        二分法，通过目标值对数组的头尾节点大小决定采用左分还与右分
      */
    public int search(int[] nums, int target) {
        int l = 0;
        int r = nums.length - 1;
        while(l <= r){
            int i = (l+r)/2;
            int index = nums[i];
            if (index == target) return i;
            if (nums[0] <= index){
                if (index > target && nums[0] <= target) r = i - 1;
                else l = i + 1;
            }else {
                if (index < target && nums[nums.length - 1] >= target) l = i + 1;
                else r = i - 1;
            }
        }
        return -1;
    }

    /**     LeetCode 153题
        二分查找
     */
    public int findMin(int[] nums) {
        int l = 0;
        int r = nums.length - 1;
        while(l <= r){
            int i = (l+r)/2;
            if (nums[i] > nums[nums.length - 1]) l = i + 1;
            else r = i - 1;
//            if (nums[0] > nums[nums.length - 1]) {
//                if (nums[i] >= nums[0]) l = i + 1;
//                if (nums[i] <= nums[nums.length - 1]) r = i - 1;
//            }else {
//                return nums[0];
//            }
        }
        return nums[l];
    }
    /**
     * LeetCode 4题
     */
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int index = (nums1.length + nums2.length - 1) / 2;
        int i = 0;
        int n1 = 0;
        int n2 = 0;
        do {
            if (nums1[n1]<= nums2[n2]) n1++;
            else n2++;
            i++;
        }while (i < index);
        return 0;
    }
}
